#pragma once

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 把key转化为整型的仿函数
template<class K>
struct HashKey 
{
  K operator()(const K& key)
  {
    return key;
  }
};

// 当key为string类型时默认调用的特化版本 
// 把每个字符的ASCLL码相加得到的整型值作为哈希的key
template<>
struct HashKey<string>
{
  size_t operator()(const string& s)
  {
    size_t sum = 0;
    for(const auto& e : s)
    {
      sum  = sum * 131 + e;
    }
    return sum;
  }
};

// 枚举，用来表示每一个位置数据的状态
enum State
{
  EXITS,
  EMPTY,
  DELATE,
};

// 封装哈希表存储数据的类型
template<class K, class V>
struct HashData
{
  pair<K, V> _kv;
  State _state = EMPTY;
};

// 哈希表主体，包含哈希表增删查改功能
template<class K, class V, class GetHashKey = HashKey<K>>
class HashTable
{
    typedef struct HashData<K, V> HashData;
  public:
    // 插入数据
    bool Insert(const pair<K, V>& kv)
    {
      // 1、先查找要插入的key是否已经存在，存在的话就不能再插入了
      if(Find(kv.first))
      {
        return false;
      }
      // 2、元素已经确认要插入，接下来需要检查空间是否足够
      //  a、空间为0，默认开10个空间
      //  b、负载因子超过0.7，增容确保有适量的空位置
      if(_table.size() == 0)// PS：不能用_n判断
      {
        _table.resize(10);
      }
      else if((double)_n / (double)_table.size() > 0.7)
      {
        HashTable<K, V, GetHashKey> newHashTable;
        newHashTable._table.resize(_table.size() * 2);
        for(const auto& e : _table)
        {
          if(e._state == EXITS)
          {
            newHashTable.Insert(e._kv);
          }
        }
        _table.swap(newHashTable._table);
      }

      GetHashKey kot;
      size_t index = kot(kv.first) % _table.size();
      while(_table[index]._state == EXITS)
      {
        ++index;
        index %= _table.size();
      }
      _n++;
      _table[index]._kv = kv;
      _table[index]._state = EXITS;
      return true;
    }

    // 删除数据
    bool Erase(const K& key)
    {
      HashData* ret = Find(key);
      if(ret)
      {
        --_n;
        ret->_state = DELATE;
        return true;
      }
      return false;
    }

    // 查找数据
    HashData* Find(const K& key)
    { 
      // 1、一个有效数据都没有的话就直接返回空
      if(_n == 0)
      {
        return nullptr;
      }
      // 2、通过输入的key线性探测，如果如果为空都没有找到说明不存在
      GetHashKey kot;
      size_t index = kot(key) % _table.size();
      while(_table[index]._state != EMPTY)
      {
        if(_table[index]._state == EXITS && _table[index]._kv.first == key)
        {
          return &_table[index];
        }
        ++index;
        index %= _table.size();
      }
      return nullptr;
    }

    // 打印哈希表数据
    void PrintfHashTable()
    {
      for(const auto& e : _table)
      {
        if(e._state == EXITS)
        {
          cout<<'<'<<e._kv.first<<", "<<e._kv.second<<'>'<<endl;
        }
      }
    }

  private:
    size_t _n = 0;// 当前有效元素个数
    vector<HashData> _table;// 存储数据的数组
};
